package com.zx._12_算法.数据结构.link;

/**
 * @version v1.0
 * @Project: knowledge
 * @Title: Demo4
 *         查找单链表中的倒数第K个节点（k > 0）（普通模式）
 * @author: zhangxue
 * @date: 2019年7月27日下午8:34:11
 * @company: 未知之地
 * @Copyright: Copyright (c) 2019
 */
public class Demo4 {

    public static void main(String[] args) {
        Node<String> node1 = new Node<>();
        Node<String> node2 = new Node<>();
        Node<String> node3 = new Node<>();
        Node<String> node4 = new Node<>();
        Node<String> node5 = new Node<>();

        node1.data = "1";
        node1.next = node2;
        node2.data = "2";
        node2.next = node3;
        node3.data = "3";
        node3.next = node4;
        node4.data = "4";
        node4.next = node5;
        node5.data = "5";

        System.out.println(getLastNode1(node1, 2));
        System.out.println(getLastNode2(node1, 2));

    }

    /**
     * @title 先获链表长度，再计算获得k的正序位置。时间复杂度为O(2n)
     * @des 假设链表长度为length, 底数第K位，正序的位置是正数的索引为length - k
     */
    public static String getLastNode1(Node<String> head, int k) {
        // 获得总长度
        Node<String> node = head;
        int length = 1;
        while (node.next != null) {
            node = node.next;
            length++;
        }
        // 计算k的位置
        int office = length - k;
        // 开始获得office
        node = head;
        for (int i = 0; i < length; i++) {
            if (i == office) {
                return node.data;
            }
            node = node.next;
        }
        return null;
    }

    /**
     * @title 对方法1进行优化，提取思想。时间复杂度为O(n)
     */
    public static String getLastNode2(Node<String> head, int k) {
        Node<String> fast = head;
        Node<String> slow = head;
        // fast先走K步
        for (int i = 0; i < k && fast != null; i++) {
            fast = fast.next;
        }
        // 说明长度不够
        if (fast == null) {
            return null;
        }
        // 先走fast长度是length-k。这里length是隐藏的
        // fast先走K步
        while (fast != null && slow != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.data;
    }


    static class Node<T> {

        T data;
        Node<T> next;
    }
}
